package dp.subsequence;

import java.util.Arrays;

//300. 最长递增子序列
public class Num300_lengthOfLIS {
 public int lengthOfLIS(int[] nums) {
     int res = 0;
     int []dp = new int[nums.length];//dp[i]表示以i结尾包括i的最长子序列的长度
     dp[0] = 1;
     for (int i = 1; i < nums.length; i++) {
         for (int j = 0; j < i; j++) {
             if (nums[i] > nums[j]){
                 dp[i] = Math.max(dp[i] , dp[j] + 1);
             }
             res = Math.max(res , dp[i]);
         }
     }
     return res;





 }
//    public int lengthOfLIS(int[] nums) {
//        if (nums.length == 1)return 1;
//        int []dp = new int[nums.length];
//        int res = 0;
//        Arrays.fill(dp , 1);
//        for (int i = 1  ; i < nums.length; i++) {
//            for (int j = 0; j < i; j++) {
//                if (nums[i] > nums[j]){
//                    dp[i] = Math.max(dp[i] , dp[j] + 1);
//                }
//            }
//            res = Math.max(res , dp[i]);
//        }
//        return res;
//    }
}
